#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 *给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：


输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */




ListNode *removeNthFromEnd(ListNode *head, int n) {
    ListNode *temp = head;
    ListNode *temp1 = head;


    while (n != 0) {
        temp = temp->next;
        if (temp == nullptr)
            //return head;
            break;
    }
    if (temp->next == nullptr && n == 0)
        return temp->next;

    while (temp->next != nullptr) {
        temp1 = temp1->next;
        temp = temp->next;
    }
    ListNode *p = temp1->next;
    temp1->val == p->val;
    temp1->next = p->next;
    delete p;
    return head;


}


ListNode *removeNthFromEnd1(ListNode *head, int n) {
    if (head->next == nullptr)
        return nullptr;

    ListNode *first = head;
    ListNode *second = head;
    //让他们同时走n-1 步
    while (n > 0 && second != nullptr) {
        second = second->next;
        n--;
    }

    //遇到尾指针跑飞的 直接返回第二节点
    if (!second) {
        return head->next;
    }
    while (second->next != nullptr) {
        first = first->next;
        second = second->next;
    }


    //获取 删除的节点
    ListNode *del = first->next;
    first->next = del->next;
    delete del;

    return head;
}


//递归写法 TODO
//(删除节点 返回删除后的头结点)
int now = 0;

ListNode *removeNthFromEnd2(ListNode *head, int n) {
    //出口 感觉他妈的国际惯例了
    if (head == nullptr || head->next == nullptr)
        return head;


    ListNode *p = removeNthFromEnd2(head->next, n);

    now++;
    if (now == n) {
        ListNode *del = head->next;
        head->next = del->next;
        delete del;
        return nullptr;
    }


    return p;
}